package ink.lovejinhu.leetcode;

import java.util.HashMap;

/**
 * @author jinhu
 * created 2021-07-21 9:46
 */
public class Solution_0506 {
    public String[] findRelativeRanks(int[] score) {

        int[] v = new int[score.length];
        for (int i = 0; i < score.length; i++) {
            v[i] = score[i];
        }

        this.quickSort(score, 0, score.length - 1);
        HashMap<Integer, String> query = new HashMap<>();
        query.put(score[score.length - 1], "Gold Medal");
        query.put(score[score.length - 2], "Silver Medal");
        query.put(score[score.length - 3], "Bronze Medal");
        for (int i = 0, j = score.length - 1; i < score.length; i++, j--) {
            query.put(score[j], i + 1 + "");
        }
        String[] res = new String[score.length];
        for (int i = 0; i < score.length; i++) {
            res[i] = query.get(v[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] test = {5, 4, 3, 2, 1};
        Solution_0506 solution_0506 = new Solution_0506();
        solution_0506.quickSort(test, 0, test.length - 1);
        for (int i = 0; i < test.length; i++) {
            System.out.println(test[i]);
        }
    }

    public void quickSort(int[] score, int left, int right) {  //什么情况下会越界
        if (left >= right) {
            return;
        }
        int l = left - 1;
        int r = right + 1;
        int mid = score[l + r >> 1];
        while (l < r) {
            do {
                l++;
            } while (score[l] < mid);
            do {
                r--;
            } while (score[r] > mid);
            if (l < r) {
                swap(score, l, r);
            }
        }
        quickSort(score, left, l - 1);
        quickSort(score, r + 1, right);
    }

    public void swap(int[] scope, int v0, int v1) {
        int temp = scope[v0];
        scope[v0] = scope[v1];
        scope[v1] = temp;
    }
}
